package com.peng.leetcode.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TotalNQueens
 *
 * @author: lupeng6
 * @create: 2020/11/27 17:26
 */
public class TotalNQueens {

    public static void main(String[] args) {
        int i = new Solution1().totalNQueens(4);
        System.out.println(i);
    }

    static class Solution1 {
        public int totalNQueens(int n) {
            int solve = solve(n, 0, 0, 0, 0);
            return solve;
        }

        private int solve(int n, int row, int exCols, int exDia1, int exDia2) {
            if (row == n) {
                return 1;
            }
            int count = 0;
            int canPutPositions = ((1 << n) - 1) & (~(exCols | exDia1 | exDia2));
            while (canPutPositions != 0) {
                int position = Integer.lowestOneBit(canPutPositions);
                canPutPositions = canPutPositions - position;
                count += solve(n, row + 1, (exCols | position), (exDia1 | position) << 1, (position | exDia2) >> 1);
            }
            return count;
        }

        private List<String> genBoard(int n, int[] queens) {
            List<String> res = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                char[] row = new char[n];
                Arrays.fill(row, '.');
                if (queens[i] >=0) {
                    row[queens[i]] = 'Q';
                }
            }
            return res;
        }
    }

    static class Solution {
        public int totalNQueens(int n) {
            return solve(n, 0, 0, 0, 0);
        }

        public int solve(int n, int row, int columns, int diagonals1, int diagonals2) {
            if (row == n) {
                return 1;
            } else {
                int count = 0;
                System.out.println(Integer.toBinaryString(columns));
                int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
                while (availablePositions != 0) {
                    System.out.println(Integer.toBinaryString(availablePositions));
                    System.out.println(Integer.toBinaryString(-availablePositions));
                    int position = availablePositions & (-availablePositions);
                    System.out.println(Integer.toBinaryString(position));
                    availablePositions = availablePositions & (availablePositions - 1);
                    count += solve(n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
                }
                return count;
            }
        }
    }

}
